//
// Created by ct on 2021/10/27.
//

#ifndef ALGOANDSTRUCT_LINKED_LIST_H
#define ALGOANDSTRUCT_LINKED_LIST_H

#include <vector>

using std::vector;
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 *
 *
 * 关于链表， 优先考虑set和优先队列
 */
typedef struct ListNode {
    int val;
    ListNode *next;

    explicit ListNode(int x) : val(x), next(nullptr) {}
    explicit ListNode(int x, ListNode *next) : val(x), next(next) {}

} listNode;

class SolutionLinkedList {
public:
    // 双指针。先判断长度，循环条件是 fast！=null && fast.next != bull; 先和slow比较在移动slow
    static bool hasCycle(listNode *head);
    // 是否有环使用set
    static bool hasCycleSet(listNode *head);

    static listNode *create_linked_list(vector<int> &nums);

    static void printLinkedList(listNode *head);
    // 使用优先级队列,默认大顶堆，因此重载 <
    // https://leetcode-cn.com/problems/merge-k-sorted-lists/
    // 合并K个升序链表
   static ListNode *mergeKLists(vector<ListNode *> &lists);
    // 合并两个升序链表
    static  ListNode* mergeTwoLists(ListNode *a, ListNode *b);
};

extern  void print();

template<typename T1, typename T2>
struct _is_same {
    static const bool value = false;
};

template<typename T>
struct _is_same<T, T> {
    static const bool value = true;
};

#endif //ALGOANDSTRUCT_LINKED_LIST_H
